package code901_1000.code10_20;

import java.util.Random;

/**
 * 给你一个整数数组 nums，请你将该数组升序排列。
 *
 * 输入：nums = [5,2,3,1]
 * 输出：[1,2,3,5]
 *
 * 输入：nums = [5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 */
public class _912sortArray {

    /**
     * 快速排序 ： 选择一个基准元素（通常为第一个），大于基准元素的在右边，小于基准元素的在左边。
     * 第一轮后就确定了第一个基准元素的位置，第二轮开始将左右两个重新进行排序，分而治之，直至结束。
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        randomizedQuickSort(nums,0,nums.length-1);
        return nums;
    }

    private void randomizedQuickSort(int[] nums, int l, int r) {
        if(l<r){
            int pos = randomizedPartition(nums,l,r);
            randomizedQuickSort(nums,1,pos-1);
            randomizedQuickSort(nums,pos+1,r);
        }
    }

    private int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r-l+1)+1; //随机选择一个元素作为我们的主元素。
        swap(nums,r,i);
        return partition(nums,l,r);
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l-1;
        for (int j = l; j <= r-1; j++) {
            if(nums[j] <= pivot){
                i = i+1;
                swap(nums,i,j);
            }
        }
        swap(nums,i+1,r);
        return i+1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    int[] tmp;

    /**
     * 归并排序：分而治之，八分四，四分二，二分一进行排序在归并。
     * 执行用时：     * 10 ms     * , 在所有 Java 提交中击败了     * 84.35%     * 的用户
     * 内存消耗：     * 47.4 MB     * , 在所有 Java 提交中击败了     * 58.87%     * 的用户
     * @param nums
     * @return
     */
    public int[] sortArray0(int[] nums){
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }

    private void mergeSort(int[] nums, int l, int r) {
        if(l>=r)return;
        int mid = (l+r)>>1;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        int i = l,j = mid + 1;
        int cnt = 0;
        while (i<=mid && j<=r){
            if(nums[i] <= nums[j]){
                tmp[cnt++] = nums[i++];
            }else {
                tmp[cnt++] = nums[j++];
            }
        }
        while (i<=mid){
            tmp[cnt++] = nums[i++];
        }
        while (j<=r){
            tmp[cnt++] = nums[j++];
        }
        for (int k = 0; k < r - l + 1; k++) {
            nums[k+l] = tmp[k];
        }
    }

}
